class Solution:
    def canPartition(self,nums):
        if sum(nums)%2 !=0:
            return False
        nums.sort()
        target=sum(nums)//2

        #题目说每个数组中的元素不会超过100，数组的大小不会超过200
        #因此不大于20000，背包大小为其中一半

        dp=[0]*1001
        for i in range(0,len(nums)): #遍历nums中的元素
            # 遍历背包容量，每一个元素一定是不可重复放入，从大到小遍历
            for i in range(target,nums[i]-1,-1):
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])

        # 集合中的元素正好可以装满容量为target的背包
        if dp[target]==target:
            return True
        return False